In modern cryptographic systems, such as the symmetric block cipher known as Rinjdael (adopted by the U.S. National Institute of Standards and Technology as its Advanced Encryption Standard or AES), blocks of data (bit strings) are subject to numerous substitution and permutation operations, which at a deeper level typically involve byte shifts, XOR additions, and congruence operations upon polynomials (represented as bit strings). Thus, in AES, finite field arithmetic over polynomials in GF(28) are performed using g(x)=x8+x4+x3+x+1 and h(x)=x8+1 as moduli. Methods of rapidly computing polynomial quotients and residues are desired for efficient operation of these cryptographic systems.
U.S. Pat. No. 6,523,053 to Lee et al. describes a method and apparatus for performing finite field polynomial division. The long polynomial is split into segments or groups, and the partial quotient and remainder are computed in parallel for each group, then combined. This technique is used for large polynomials (of high degree).
U.S. Pat. Nos. 5,615,220 to Pharris and 5,185,711 to Hattori perform finite field division using Euclid's algorithm, which is a technique that involves multiple iterations of divisions. The technique is useful for divisions involving large polynomials.